package 剑指offer.堆栈队列;


import java.util.Stack;

public class 第30题解法2 {

    /*
     * 给定数据范围，例如 -100000 ~ 100000 之间
     * 那么可以把代码优化到 S(1)
     *
     * 代码的核心思想是入栈的数据不是原始值，而是差值
     * 差值 = 栈顶值 - 最小值
     */

    private Stack<Integer> stack = new Stack<>();
    private int min;

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
            stack.push(0);
        } else {
            // 计算差值
            int compare = x - min;
            stack.push(compare);
            // 如果差值小于0，显然 x 成为最小值，否则最小值不变
            min = compare < 0 ? x : min;
        }
    }

    public int pop() {
        int top = stack.peek();
        // 如果top小于0，显然最小值也一并会被删除，此时更新最小值
        min = top < 0 ? (min - top) : min;
        return stack.pop() + min;
    }

    public int getMin() {
        return min;
    }

    public static void main(String[] args) {
        第30题解法2 stack = new 第30题解法2();
        stack.push(2);
        stack.push(1);
        stack.push(3);
        stack.push(0);

        for (int i = 0; i < 4; i++) {
            System.out.printf("第%d次：min=%d, pop=%d\n", i, stack.getMin(), stack.pop());
            System.out.printf("第%d次之后，min=%d\n", i, stack.getMin());
            System.out.println();
        }

    }

}
